#include<iostream>
#include<vector>
using namespace std;


//int singleNumber(vector<int>& nums) {
//	int i = 0;
//	for (auto item : nums)
//	{
//		i ^= item;
//	}
//	return i;
//}

vector<vector<int>> generate(int numRows) {
	vector<vector<int>> ret;
	for (int i = 0; i < numRows; i++)
	{
		ret.push_back(vector<int>(i + 1, 1));
		for (int j = 1; j < i ; j++)
		{
			if (i > 1)
			{
				ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
			}
		}
	}
	return ret;
}

int removeDuplicates(vector<int>& nums) {
	int pos = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (i > 0)
		{
			if (nums[i] != nums[i - 1])
			{
				nums[pos++] = nums[i];
			}
		}
		else
		{
			nums[pos++] = nums[i];
		}
	}

	return pos;

}



vector<int> singleNumber(vector<int>& nums) {
	int des = 0;
	int find = nums.size() - 1;
	int pos = find;
	int ret[2] = {0};
	int count = 0;
	while (true)
	{
		if (find == des)
		{
			ret[count] = nums[des];
			count++;
			des++;
			find = pos;
			if (count == 2)
			{
				nums.clear();
				nums.push_back(ret[0]);
				nums.push_back(ret[1]);
				return nums;
			}
				
		}
		else if (nums[find] == nums[des])
		{
			int temp = nums[pos];
			nums[pos] = nums[des];
			nums[find] = temp;
			des++;
			find = --pos;
		}
		else if (nums[find] != nums[des])
		{
			find--;
		}
		
	}

}


void sort(vector<int>& numbers,int left,int right)
{
	int start = left;
	int end = right;
	if (left >= right)
	{
		return;
	}
	int pos = left;
	while (true)
	{
		if (right == left)
		{
 			int temp = numbers[left];
			numbers[left] = numbers[pos];
			numbers[pos] = temp;
			sort(numbers, start, left - 1);
			sort(numbers, left + 1, end);
			return;
		}
		if (numbers[right] < numbers[pos])
		{
			while (true)
			{
				if (right == left)
				{
					int temp = numbers[left];
					numbers[left] = numbers[pos];
					numbers[pos] = temp;
					sort(numbers, start, left - 1);
					sort(numbers, left + 1, end);
					return;
				}
				left++;
				if (numbers[left] > numbers[pos])
				{
					int temp = numbers[left];
					numbers[left] = numbers[right];
					numbers[right] = temp;
					break;
				}

			}
		}
		right--;

	}


}

int MoreThanHalfNum_Solution(vector<int>& numbers) {
	sort(numbers, 0, numbers.size() - 1);
	int ret = numbers.size() / 2 ;
	if (numbers.size()!=0)
	{
		return numbers[ret];
	}
	return 0;
}

int main()

{

	int ar[] = { 9,9,9,9,2,5 };

	int n = sizeof(ar) / sizeof(int);

	vector<int> v(ar, ar + n);

	//cout << v[10];

	//generate(4);

	//int length = removeDuplicates(v);
	//singleNumber(v);
	MoreThanHalfNum_Solution(v);

	
}